1324E - Sleeping Schedule - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bit(i, x) (x >> i & 1)
#define _unique(x) (x).resize(unique((x).begin(), (x).end()) - (x).begin());
#define all(x) (x).begin(), (x).end()
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
const int N = 3e5 + 3;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) {
    return l+rng()%(r-l+1);
}
template<typename T> void cmax(T &a, T b) {a = max(a, b);}



int n, h, l, r;
int a[N];
int mark[N];
int res;
int dp[2002][2002];
bool vst[2002][2002];

void Process() {
    int cur = 0, sum = 0;
    for(int i = 1; i <= n; i++) {
        if (mark[i] == 0) cur += a[i];
        else cur += a[i] - 1;
        cur %= h;
        if (cur >= l && cur <= r) sum++;
    }
    res = max(res, sum);
//    cout << endl;
}

void backtrack(int p) {
    if (p > n) {
        Process();
        return;
    }
    backtrack(p + 1);
    mark[p] = 1;
    backtrack(p + 1);
    mark[p] = 0;
}

int Dp(int i, int j) {
    if (i == 0) return dp[i][j];
    if (vst[i][j] == 1) return dp[i][j];
    auto &cur = dp[i][j];
    int u = ((j - a[i]) % h + h) % h;
    int v = ((j - a[i] + 1) % h + h) % h;
    cur = max(cur, Dp(i - 1, u) + (j >= l && j <= r));
    cur = max(cur, Dp(i - 1, v) + (j >= l && j <= r));
    vst[i][j] = 1;
    return cur;
}

void solve() {
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j < h; j++) {
            dp[i][j] = -1e9;
        }
    }
    dp[0][0] = 0;
//    for(int i = 1; i <= n; i++) {
//        for(int j = 0; j < h; j++) {
//            auto &cur = dp[i][j];
//            int u = ((j - a[i]) % h + h) % h;
//            int v = ((j - a[i] + 1) % h + h) % h;
//            cur = max(cur, dp[i - 1][u] + (j >= l && j <= r));
//            cur = max(cur, dp[i - 1][v] + (j >= l && j <= r));
//        }
//    }
    for(int j = 0; j < h; j++) {
//        res = max(res, dp[n][j]);
        res = max(res, Dp(n, j));
    }
    cout << res << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);

//    freopen("testing.txt", "r", stdin);
//    freopen("outputing.txt", "w", stdout);
    #define task ""
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
//    #define Kawaii
    #ifdef Kawaii
        auto starttime = chrono::high_resolution_clock::now();
    #endif

    int test = 1; //cin >> test;
    while (test--) {
        cin >> n >> h >> l >> r;
        for(int i = 1; i <= n; i++) cin >> a[i];
//        for(int i = 1; i <= n; i++) a[i] = rnd(1, 1000);

//        for(int i = 1; i <= n; i++) cout << a[i] << " ";
        solve();
    }

    // Each pos have 2 choice
    // Same choice but cur time may different
    // (i, cur) best answer in iTh pos with cur time






    #ifdef Kawaii
        auto endtime = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
        cout << "\n=====" << "\nUsed: " << duration << " ms\n";
    #endif

    return 0 ^ 0;
}